package com.wyw.learning.offer;

import java.util.Stack;

/**
 * 用两个栈实现一个队列
 *      appendTail  完成在队列尾部插入整数
 *      deleteHead  完成在队列头部删除整数（若队列中没有元素，操作返回-1）
 *
 * 如果你使用Stack的方式来做这道题，会造成速度较慢；
 *  原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。
 *  可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/14 10:28
 */
public class Offer009 {

//    LinkedList<Integer> stack1;
//    LinkedList<Integer> stack2;
//
//    public Offer009(){
//        stack1 = new LinkedList<>();
//        stack2 = new LinkedList<>();
//    }
//
    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if(stack2.isEmpty()) {
            if (stack1.isEmpty()) {
                return -1;
            }
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        } else {
            return stack2.pop();
        }
    }

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public Offer009(){
        stack1 = new Stack();
        stack2 = new Stack();
    }
}
